第三篇图与网络的学习笔记，同最短路问题一样，都是图论中的经典之经典——“最小生成树”！！！ 还是把握两个大方向：“数学+代码”，冲！！！

树（tree）是图论中非常重要的一类图，它非常类似于自然界中的树，结构简单、应用广泛，最小生成树问题则是其中的经典问题之一。在实际应用中，许多问题的图论模型都是最小生成树，如通信网络建设、有线电缆铺设、加工设备分组等。

【定义 3.1】 连通的无圈图称为树。 例如，下图给出的 是树，但 G 1 G1 G1和 G 2 G2 G2则不是树。 【定理3.1】 设 G G G是具有 n n n个顶点 m m m条边的图，则以下命题等价。 （1）图 G G G是树； （2）图 G G G中任意两个不同顶点之间存在唯一的路。 （3）图 G G G连通，删除任一条边均不连通； （4）图 G G G连通，且 n = m + 1 n=m+1 n=m+1； （5）图 G G G无圈，添加任一条边可得唯一的圈； （6）图 G G G无圈，且 n = m + 1 n=m+1 n=m+1。

【定义3.2】 若图 G G G的生成子图 H H H是树，则称 H H H为 G G G的生成树或支撑树。 一个图的生成树通常不唯一。

【定理3.2】 连通图的生成树一定存在。 方法：破圈法

【证明】 给定连通图 G G G，若 G G G无圈，则 G G G本身就是自己的生成树。若 G G G有圈，则任取 G G G中一个圈 C C C，记删除 C C C中一条边后所得之图为 G ′ G' G′。显然 G ′ G' G′中圈 C C C已经不存在，但 G ′ G' G′仍然连通。若 G ′ G' G′中还有圈，再重复以上过程，直至得到一个无圈的连通图 H H H。易知 H H H是 G G G的生成树。

【定义3.3】 在赋权图 G G G中，边权之和最小的生成树称为 G G G的最小生成树。 n n n个顶点的完全图，其不同的生成树的个数为 n n − 2 n^{n-2} nn−2。 不能枚举

对于赋权图 G = ( V , E , W ) G=(V,E,W) G=(V,E,W)，其中 V V V为顶点集合， E E E为边的集合， W W W为邻接矩阵，这里顶点集合 V V V中有 n n n个顶点，下面构成它的最小生成树——所有生成树中所有边上权重和最小的生成树。

Kruskal算法思想——每次将一条权最小的边加入子图 T T T中，并保证不形成圈。 方法：避圈法

Kruskal算法如下： （1） 选 e 1 ∈ E e_1∈E e1​∈E，使得 e 1 e_1 e1​是权值最小的边。 （2） 若 e 1 , e 2 , ⋯ , e i e_1,e_2,⋯,e_i e1​,e2​,⋯,ei​已选好，则从 E − e 1 , e 2 , ⋯ , e i E-{e_1,e_2,⋯,e_i} E−e1​,e2​,⋯,ei​中选取 ，使得 ① e 1 , e 2 , ⋯ , e i , e i + 1 {e_1,e_2,⋯,e_i,e_{i+1}} e1​,e2​,⋯,ei​,ei+1​中无圈，且 ② e i + 1 e_{i+1} ei+1​是 E − e 1 , e 2 , ⋯ , e i E-{e_1,e_2,⋯,e_i} E−e1​,e2​,⋯,ei​中权值最小的边。 （3） 直到选得 e n − 1 e_{n-1} en−1​为止。

集合 P P P存放 G G G的最小生成树中的顶点 集合 Q Q Q存放 G G G的最小生成树中的边 令集合 P P P的初值为 P = v 1 P={v_1} P=v1​（假设构造最小生成树时，从顶点 v 1 v_1 v1​出发），集合 Q Q Q的初值为 Q = Φ Q=Φ Q=Φ（空集）。

Prim算法的思想——从所有 p ∈ P p∈P p∈P， v ∈ V − P v∈V-P v∈V−P的边中，选取具有最小权值的边 p v pv pv，将顶点 v v v加入集合 P P P中，将边 p v pv pv加入集合 Q Q Q中，如此不断重复，直到 P = V P=V P=V时，最小生成树构造完毕，这时集合 Q Q Q中包含了最小生成树的所有边。

Prim算法如下： （1） P = v 1 P={v_1} P=v1​， Q = Φ Q=Φ Q=Φ； （2） w h i l e P   = V while P~=V whileP =V \qquad 找最小边 p v pv pv，其中 p ∈ P , v ∈ V − P p∈P,v∈V-P p∈P,v∈V−P； P = P + v \qquad P=P+{v} P=P+v； Q = Q + p v \qquad Q=Q+{pv} Q=Q+pv； e n d \qquad end end

【例3.1】 一个乡有9个自然村，其间道路及各道路长度如图4.11所示，各边上的数字表示距离，问架设通信线时，如何拉线才能使用线最短。

【解】 这就是一个最小生成树的问题，用Kruskal算法求解。先将边按大小顺序由小至大排列： 然后按照边的顺序排列，取定： 取边原则——先小后大，避圈

由于下一个未选中的最小权边 ( v 0 , v 3 ) (v_0,v_3) (v0​,v3​)与已选边 e 1 , e 2 e_1,e_2 e1​,e2​构成圈，所以排除，选 e 8 = ( v 6 , v 7 ) e_8=(v_6,v_7) e8​=(v6​,v7​)，得到下图，就是图 G G G的一棵最小生成树，它的权是13。 基于邻接矩阵构成图的MATLAB程序如下：

基于边的细胞数组构造图的MATLAB程序如下：

代码效果：

顶点 v 1 v_1 v1​表示树根，总共有 n n n个顶点。顶点 v i v_i vi​到顶点 v j v_j vj​边的权重用 w i j w_{ij} wij​表示，当两个顶点之间没有边时，对应的权重用 M M M（充分大的正实数）表示，这里 w i i = M , i = 1 , 2 , ⋯ , n w_ii=M,i=1,2,⋯,n wi​i=M,i=1,2,⋯,n。 引入0-1变量 x i j = { 1 当 从 v i 到 v j 的 边 在 树 中 0 , 当 从 v i 到 v j 的 边 不 在 树 中 x_{ij}= \begin{cases} 1 & 当从v_i到v_j的边在树中 \\ 0, & 当从v_i到v_j的边不在树中 \\ \end{cases} xij​={10,​当从vi​到vj​的边在树中当从vi​到vj​的边不在树中​ 目标函数是使得 z = ∑ i = 0 n ∑ j = 0 n w i j x i j z =\sum_{i=0}^n {\sum_{j=0}^n {w_{ij}x_{ij}}} z=∑i=0n​∑j=0n​wij​xij​最小化 约束条件分成如下4类： （1）根v_1至少有一条边连接到其他的顶点， ∑ j = 0 n x 1 j = 1 \sum_{j=0}^n {x_{1j}}=1 j=0∑n​x1j​=1

（2）除根外，每个顶点只能有一条边进入， ∑ i = 0 n x i j = 1 , j = 2 , . . . , n . \sum_{i=0}^n {x_{ij}}=1,j=2,...,n. i=0∑n​xij​=1,j=2,...,n.

以上两约束条件是必要的但非充分的 可保证边数为顶点个数-1，但不能保证无圈

需要增加一组变量 u j ( j = 1 , 2 , ⋯ , n ) u_j (j=1,2,⋯,n) uj​(j=1,2,⋯,n)，再附加约束条件：

（3）限制 u j u_j uj​的取值范围为： u 1 = 0 ,   1 ≤ u i ≤ n − 1 ,   i = 2 , 3 , ⋯ , n u_1=0, 1≤u_i≤n-1, i=2,3,⋯,n u1​=0, 1≤ui​≤n−1, i=2,3,⋯,n.

（4）各条边不构成子圈， u i − u j + n x i j ≤ n − 1 ,   i = 1 , ⋯ , n , j = 2 , ⋯ , n . u_i-u_j+nx_{ij}≤n-1, i=1,⋯,n,j=2,⋯,n. ui​−uj​+nxij​≤n−1, i=1,⋯,n,j=2,⋯,n.

最小生成树的0-1帧数规划问题模型如下： z = ∑ i = 0 n ∑ j = 0 n w i j x i j ′ z =\sum_{i=0}^n {\sum_{j=0}^n {w_{ij}x'_{ij}}} z=i=0∑n​j=0∑n​wij​xij′​ s . t . { ∑ j = 0 n x 1 j = 1 ∑ i = 0 n x i j = 1 j = 2 , . . . , n . u 1 = 0 ,   1 ≤ u i ≤ n − 1 ,   i = 2 , 3 , ⋯ , n . u i − u j + n x i j ≤ n − 1 ,   i = 1 , ⋯ , n , j = 2 , ⋯ , n . x i j = 0 或 1 ， i , j = 1 , 2 , . . . , n . s.t. \begin{cases} \sum_{j=0}^n {x_{1j}}=1\\ \sum_{i=0}^n {x_{ij}}=1 &j=2,...,n. \\ u_1=0, 1≤u_i≤n-1, &i=2,3,⋯,n. \\ u_i-u_j+nx_{ij}≤n-1, &i=1,⋯,n,j=2,⋯,n. \\ x_{ij}=0或1，&i,j=1,2,...,n. \\ \end{cases} s.t.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​∑j=0n​x1j​=1∑i=0n​xij​=1u1​=0, 1≤ui​≤n−1, ui​−uj​+nxij​≤n−1, xij​=0或1，​j=2,...,n.i=2,3,⋯,n.i=1,⋯,n,j=2,⋯,n.i,j=1,2,...,n.​

代码如下（示例）：

【例3.2】 利用数学规划模型求解例4.12。一个乡有9个自然村，其间道路及各道路长度如图4.11所示，各边上的数字表示距离，问架设通信线时，如何拉线才能使用线最短。